package com.aug_leo.datastructure.linkedlist;

/**
 * 反转链表
 */
public class E01Leetcode206 {
    // 方法1

    /**
     * <h3>方法一</h3>
     * 构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的
     *
     * @param o1 旧链表的头节点
     * @return 新链表的头节点
     */
    public ListNode reverseList1(ListNode o1) {
        ListNode n1 = null;
        ListNode pointer = o1;
        while (pointer != null) {
            n1 = new ListNode(pointer.val, n1);
            pointer = pointer.next;
        }
        return n1;
    }

    /**
     * <h3>方法二</h3>
     * 与方法一类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的
     * 区别在于原题目未提供外层的容器类，这个提供一个，另外一个区别是并不去构造新节点
     *
     * @param head 旧链表的头节点
     * @return 新链表的头节点
     */
    public ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        /**
         * 向头部添加节点
         *
         * @param first 要新增在头部的节点
         */
        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }

    }

    /**
     * <h3>方法3 - 递归</h3>
     * 递归，在归时让 5 -> 4 -> 3
     *
     * @param pointer 链表头节点
     * @return 最后一个节点
     */
    public ListNode reverseList3(ListNode pointer) {
        if (pointer == null || pointer.next == null) {
            return pointer; // 最后节点
        }
        ListNode last = reverseList3(pointer.next);
        pointer.next.next = pointer;
        pointer.next = null;
//        last.next = pointer;
        return last;
    }

    /**
     * <h3>方法4</h3>
     * 从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束
     *
     * @param o1 旧链表的头节点
     * @return 新链表的头节点
     */
    public ListNode reverseList4(ListNode o1) {
        // 1.空链表    2.一个元素
        if (o1 == null || o1.next == null) {
            return o1;
        }
        // 1、设置指针o1(旧头)、n1(新头)、(旧老二)，分别指向第一，第一，第二节点
        ListNode o2 = o1.next; // 旧链表的第二个节点
        ListNode n1 = o1; // 新链表的头节点
        while (o2 != null) {
            // 2、将o2节点从链表断开，即o1节点指向第三节点
            o1.next = o2.next;
            // 3、o2节点链如链表头部
            o2.next = n1;
            // 4、n1指向o2
            n1 = o2;
            // 5、o2指向o1的下一个节点
            o2 = o1.next;
            // 6、重复以上2~5步，知道o2指向null
        }
        // 7、还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑
        return n1;
    }

    /**
     * <h3>方法5</h3>
     * 把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移
     *
     * @param o1 原链表的首节点
     */
    public ListNode reverseList5(ListNode o1) {
        // 1.空链表    2.一个元素
        if (o1 == null || o1.next == null) {
            return o1;
        }

        // 1、n1指向null，代表新链表一开始没有元素，o1指向原链表的首节点
        ListNode n1 = null;
        while (o1 != null) {
            // 2、开始循环，o2指向原链表的次节点
            ListNode o2 = o1.next;
            // 3、搬移
            o1.next = n1;
            // 4、指针复位
            n1 = o1;
            // 4、指针复位
            o1 = o2;
            // 5、重复2~4步
        }
        // 6、当o1 == null 时退出循环
        return n1;
    }


    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new E01Leetcode206().reverseList5(o1);
        System.out.println(n1);
    }

}
